import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 沈明月
 * Date: 2022-11-25
 * Time: 18:41
 */
public class TestOne {
//消失的数字
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//示例：
// 输入：[3,0,1]--->输出：2
//输入：[9,6,4,2,3,5,7,0,1]--->输出：8


//法一：考虑到nums数组包含了0~n的所有整数，这说明数组的每一个元素都会和相对应的这个下标相等，如果不是相等，就说明是缺失了的数字
    public static int missingNumber1(int[] nums) {
        //先排序：
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //如果缺失的数字不是最后一个的话，就可以通过i和num[i]来比较，从而判断出缺失的是哪一个；否则缺失的就是在最后
            if (i != nums[i]) {
                return i;
            }
        }
        return nums.length;
    }

    public static void main1(String[] args) {

        int[] nums = {0, 2, 3, 1, 5, 6};
        int ret1 = missingNumber1(nums);
        System.out.println(ret1);
    }


//法二：既然是0~n所有的数字都有，那就意味着它是一个等差数列，可以轻易求出前n项和，然后再对nums数列里面的元素进行相减，减剩下的就是哪个缺少的
    public static int missingNumber2(int[] nums) {
        int sum = (0 + nums.length) * (nums.length + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            sum -= nums[i];
        }
        return sum;
    }

    public static void main2(String[] args) {
        int[] nums = {0, 2, 3, 1, 5, 6};
        int ret2 = missingNumber2(nums);
        System.out.println(ret2);
    }
}
